#include <iostream>
#include <algorithm>
using namespace std;

const int n = 10; // 物品数量
int b[] = {4, 3, 6, 7, 4, 3, 5, 1, 7, 6}; // 体积
int w[] = {2, 3, 8, 9, 4, 7, 4, 3, 8, 9}; // 重量
int v[] = {4, 8, 3, 4, 9, 7, 3, 2, 9, 9}; // 价值

const int C = 25; // 最大重量
const int D = 25; // 最大体积

int m[n][C][D]; // 最优结果

int x[n]; // 01向量

void knapsack()
{
    int i, j, k;
    int maxJ = w[n - 1], maxK = b[n - 1];
    for (j = 0; j < C; j++)
    {
        for (k = 0; k < D; k++)
        {
            if (j >= maxJ && k >= maxK)
            {
                m[n - 1][j][k] = w[n - 1];
                continue;
            }
            m[n - 1][j][k] = 0;
        }
    }

    for (i = n - 1; i > 0; i--)
    {
        maxJ = w[i - 1], maxK = b[i - 1];
        for (j = 0; j < C; j++)
        {
            for (k = 0; k < D; k++)
            {
                if (j >= maxJ && k >= maxK)
                {
                    m[i - 1][j][k] = max(m[i][j][k], m[i][j - w[i - 1]][k - b[i - 1]] + v[i - 1]);
                    continue;
                }
                m[i - 1][j][k] = m[i][j][k];
            }
        }
    }

    // for (i = 1; i <= n; i++)
    //     cout << i << " " << m[n - i][C - 1][D - 1] << endl;

    j = C - 1, k = D - 1;
    for (i = 0; i < n - 1; i++)
    {
        // printf("%d %d %d %d %d \n", i, j, k, m[i][j][k], m[i + 1][j][k]);
        if (m[i][j][k] == m[i + 1][j][k])
            x[i] = 0;
        else
        {
            x[i] = 1;
            j -= w[i];
            k -= b[i];
        }
    }
    x[n - 1] = (m[n - 1][j][k] > 0) ? 1 : 0;

    for (i = 0; i < n; i++)
        cout << i << " " << x[i] << endl;

}

int main()
{
    knapsack();
}